Masala #0563

Azimjon bosh qotirmalarga qiziqadi. U bir kuni akasi bilan shunday o'yin o'ynadiki o'yinda $n$ ta uy bor, uylar 1 dan $n$ gacha o'sish tartibida raqamlangan, bu uylarning ichida $k$ tadan tuzoq bor. Azimjonning akasi $A$ raqamli uyga sovg'a yashirgan. Azimjon sovg'ani olguncha eng kamida nechta tuzoqni bosib utishi kerak. Azimjon bu o'yinda optimal (eng yaxshi) o'yinchi deb hisoblansin.

Azimjonga yordam sifatida, akasi sovg`ali xonadan tashqari hamma xonaga > yoki < belgili plakat ilib chiqdi > belgisi, qidirilayotgan xona teparoqda

< belgisi qidirilayotgan xona pastroqda ekanligini anglatadi
Uy raqamlari tartiblangan holda bo'ladi. Azimjonnig uzi bu ishni uddalay olmaydi, siz Azimjonga yordam bering.

Bitta qatorda $n$, $k$ va $A$ butun sonlari. $(1 \le A \le n \le 10^{18}, 1 \le k \le 5000)$

Bitta qatorda Azimjonning eng yaxshi usul bilan tushungan tuzoqlar soni.